package com.example.algorithm.backtracing;

import java.util.*;
import java.util.function.IntFunction;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。
 * 输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
 * <p>
 * 示例 1:
 * 输入: [1,1,2,2,2]
 * 输出: true
 * 解释: 能拼成一个边长为2的正方形，每边两根火柴。
 * <p>
 * 示例 2:
 * 输入: [3,3,3,3,4]
 * 输出: false
 * 解释: 不能用所有火柴拼成一个正方形。
 * <p>
 * 注意:
 * 给定的火柴长度和在 0 到 10^9之间。
 * 火柴数组的长度不超过15。
 */
public class Leetcode473_MakeSquare {
    public static void main(String[] args) {
        int[] matchsticks = {1, 1, 2, 2, 2};

        System.out.println(new Solution().makesquare(matchsticks));


    }
    static class Solution {

        private int[] sums = new int[4];
        private int sidelength = 0;

        /**
         * 位运算
         * 1.使用位运算构造出所有和为 target( 总和 1 4 的火柴棍的组合 存储在 validSubset 中 这就是 候选边 的组合
         * 2.validSubset 两两对比
         *   如果 (validSubList[i] & validSubList[j] = 0) 说明 i j 两条边没有选择同样的火柴棍(按位与结果为0)可以代表两条可以满足条件且同时存在的边,
         *   将 (validSubList[i] | validSubList[j]) 加入 validHalf 集合中 存储着所有 满足一半结果 的情况
         * 3.validHalf 两两对比 如果存在 (validHalf[i] & validHalf[j] = 0 )返回 true 说明有四个满足条件的边 可组成 正方形 否则返回 false
         * @param matchsticks
         * @return
         */
        public boolean makesquare3(int[] matchsticks) {
            if (matchsticks == null || matchsticks.length < 4) {
                return false;
            }

            int sum = 0;
            for (int i = 0; i < matchsticks.length; i++) {
                sum += matchsticks[i];
            }
            if (sum % 4 != 0) return false;
            int targetSideLength = sum / 4;
            List<Integer> validSubList = new ArrayList<>();// 用来存储备选集合(二进制位i为1代表 matchsticks[i] 在该子组合中)
            List<Integer> validHalfSubList = new ArrayList<>();// 用来存储备选集合两两合并后的数组
            int all = 1 << matchsticks.length;// n 个火柴棍，每个有分配不分配两种情况，一共有 2^n 种，表示为二进制是 1(n 个 0), 1-2^n 各自代表一个子组合
                                              // {1, 1, 2, 2, 2}  13(二进制1101) 就代表 {1, 1, 2(第二个2)}这个子组合

            /**
             * 1.寻找到所有火柴棍之和等于targetSideLength的子组合加入到validSubset中
             */
            for (int i = 1; i < all; i++) {// 对于每一种可能的组合，找到需要的火柴棍
                int bucketSum = 0; // 临时记录一个组合火柴棍的长度
                for (int j = 0; j < matchsticks.length; j++) { // 在寻找一个可能的集合时需要遍历火柴棍集合
                    if ((i & (1 << j)) != 0) { // 说明在该种组合中要有
                        bucketSum += matchsticks[j];
                    }
                }
                if (bucketSum == targetSideLength) //判断当前组合是否可以作为备选组合
                    validSubList.add(i);
            }

            /**
             * 2.validSubList 两两对比找到不会有重复的火柴棍的子组合
             */
            for (int i = 0; i < validSubList.size(); i++) {
                for (int j = 0; j < validSubList.size(); j++) {
                    if ((validSubList.get(i) & validSubList.get(j)) == 0) {// 两个子组合之间没有重复的火柴棍
                        validHalfSubList.add((validSubList.get(i) | validSubList.get(j)));
                    }
                }
            }

            /**
             * validHalfList 两两对比
             */
            for (int i = 0; i < validHalfSubList.size(); i++) {
                for (int j = 0; j < validHalfSubList.size(); j++) {
                    if ((validHalfSubList.get(i) & validHalfSubList.get(j)) == 0) {
                        return true;
                    }
                }
            }

            return false;
        }

        /**
         * 解法二:回溯法
         *
         * 剪枝思路:
         * 1：n个火柴棍长度总和对4取余需为0，否则返回假
         * 2：火柴杆从大到小排序，先尝试大的减少回溯可能
         * 3：每次放置时，每条边上不可放置超过总和1/4的火柴棍
         *
         * @param matchsticks
         * @return
         */
        public boolean makesquare2(int[] matchsticks) {
            if (matchsticks == null || matchsticks.length < 4) {
                return false;
            }

            int sum = 0;
            for (int i = 0; i < matchsticks.length; i++) {
                sum += matchsticks[i];
            }
            sidelength = sum / 4;

            if (sum % 4 != 0) { // 总长度不够4整除,不可能构成正方形(优化一)
                return false;
            }
            // 将数组从大到小排序后转成List(优化二)
            List<Integer> list = Arrays.stream(matchsticks).boxed()
                    .sorted(Comparator.reverseOrder()).collect(Collectors.toList());
            // 等价下面的代码
//            List<Integer> list = Arrays.stream(matchsticks).boxed().collect(Collectors.toList());
//            Collections.sort(list, Collections.reverseOrder());

            return backTrace(list, 0);
        }

        private boolean backTrace(List<Integer> list, int index) {
            if (list.size() == index) { // 递归结束条件(四个桶中的火柴棍长度之和都相同)
                return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == sums[3];
            }

            Integer e = list.get(index);
            for (int i = 0; i < 4; i++) {
                if (sums[i] + e <= sidelength) { // 每次放置时，每条边上不可放置超过总和1/4的火柴棍
                    sums[i] += e;
                    if (backTrace(list, index + 1)) { // 某次组合满足四个桶中的火柴棍长度之和都相同,说明可以组成正方形
                        return true;
                    }
                    sums[i] -= e; // 本次组合不可以组成正方形时恢复状态
                }
            }

            return false; // 遍历完所有组合都不满足,返回false
        }

        /**
         * 解法一:暴力法(超时)
         * 将火柴棍递归的分发到4个桶里
         * 每个桶里分发至少1根火柴棍
         * 在n根火柴棍分发完后，检查4个桶里火柴棍长度和是否相同，若相同，返回true
         * 这样递归完成后，就得到了所有的可能的组合
         *
         * @param matchsticks
         * @return
         */
        public boolean makesquare1(int[] matchsticks) {
            if (matchsticks == null || matchsticks.length < 4) {
                return false;
            }

            int sum = 0;
            for (int i = 0; i < matchsticks.length; i++) {
                sum += matchsticks[i];
            }
            sidelength = sum / 4;

            // 将数组转成List
            List<Integer> list = Arrays.stream(matchsticks).boxed().collect(Collectors.toList());

            return dfs(list, 0);
        }

        private boolean dfs(List<Integer> list, int index) {
            if (list.size() == index) { // 递归结束条件(四个桶中的火柴棍长度之和都相同)
                return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == sums[3];
            }
            int e = list.get(index); // 获取当前要进行分配的火柴棍
            for (int i = 0; i < 4; i++) {
                sums[i] += e; // 将火柴棍加入到某个桶中
                if (dfs(list, index + 1)) { // 某次组合满足四个桶中的火柴棍长度之和都相同,说明可以组成正方形
                    return true;
                }
                sums[i] -= e; // 本次组合不满足条件时复原桶的状态
            }

            return false; // 遍历完所有组合都不满足,返回false
        }

        public boolean makesquare(int[] matchsticks) {
            return makesquare3(matchsticks);
        }
    }
}

